However, there are only three orbits under the group D₆ since

Under D₆.

This is where our equivalence under the group definition comes into play by both of these necklaces form a single orbit. Thus, g(A) =B. And g(B) = A. Thus, we could get all 20 arrangements from 4 different hexagons, but we could get all 20 necklaces from just 3 hexagons.

These examples are simple and we can obtain this information through simple observations. But, what about obtaining information from more complicated examples?

First we need to introduce some notation.

Old Notation:

If G is a group of permutations on a set S and s Î S, then

G_s = {g Î G: g(s) = s} (Note: This is our old definition of Stabilizer)

and O_s = {g(s) : g Î G}. (Note: This is our old definition of Orbit)

New Notation:

If G is a group of permutations on a set S and g Î G, then

fix (g) = {s Î S : g(s) = s}.

This set is called the elements fixed by g.

If G is a finite group of permutations on a set S and N is the number of orbits of G on S, Then

Proof:

Let the set A be all (x, g) with s Î S, g Î G, and g(s) = s. We count A in two different ways. First, for each g Î G, the number of pairs is exactly the order of fix (g), as s runs over S. So,

g Î G

The second way to count these pairs is for each s Î S, the order of G_s is equal to the number of pairs of (s,g), as g runs over G. Thus,

sÎ S

If x₁, x₂, …, x_n is a chosen set of representatives where each x_i , (where

i = 1, 2, …, n) is from each orbit of S under G, and x is in the same orbit as x_j, then O_X = O_Xj and the number of G_X = number of G_Xj.

A theorem used from last semester tells us

Hence,

gÎ G xÎ S

(Remember that N is the number of orbits).

Perhaps this can be better shown from a chart.

If we go back to our hexagon example and label the vertices with letters this time, our hexagon would look like:

F C

E D

Out set is S = { A, B, C, D, E, F }

Let our group be G = {e, l_h}.

Our notation of (s, g) is for all s Î S (like A Î S for this example), and

g Î G (like e Î G for this example).

If we put a value of 1 in the (s, g) position if g(s) = s and 0 in the entries otherwise, our chart looks as follows:

Notice g(s) = s is the definition of fix (g).

G_s = the sum of the bottom totals. That is,

G_s = 1+1+2+1+1+2 = 8

Furthermore, the fix (g) = 6+2 = 8.

Our proof is complete.

Since our proof is complete, we can use Burnside’s Theorem.

If we apply this theorem to our example of the hexagon with our black and white vertices, we can show that the number of orbits is 4. Remember we have 20 arrangements of these vertices by rotations. Thus, our group is now G= {e, r _{(P /3)}, r _{(2P /3)}, r P , r _{(4P /3)}, r _{(5P /3)}).

If we make a chart for this, it would look like:

e 20

r P 0

r _{(4P /3)} 2

r _{(5P /3)} 0

Using Burnside’s Theorem:

N = 1/6 (20+0+2+0+2+0) = 24/6 = 4

It worked and we got the same answer as our observed answer.

Now we will see if Burnside’s Theorem will work for counting the number of orbits of our necklaces. We said earlier that the equivalence under the group D₆ gave us 3 different necklaces.

Our new group is G= { e, r P , r _{(2P /3)} or r _{(4P /3)}, r _{(P /3)} or r _{(5P /3)}, reflect across diagonal, reflect across side bisector}.

Our new chart looks like:

r P 1 0

r _{(2P /3)}

or r _{(4P /3)} 2 2

r _{(P /3)}

or r _{(5P /3)} 2 0

R diagonal 3 4

R side bisector 3 0

Using Burnside’s Theorem we get

N = 1/12 (1· 20 + 1· 0 + 2· 2 + 2· 0 + 3· 4 + 3· 0) = 36/12 = 3

And we can see that Burnside’s theorem gives us the answer we had before for this too.

Who uses Burnside’s theorem?

Mathematicians, chemists, and engineers. Chemists use it to count molecules and engineers can use it to count permutations of circuit switches.

So far everything we have done is pretty informal. To make our counts formal:

Let G be a group, S a set of objects and G acts on S if there exists a homomorphism f : G ® sym (S)

Where sym (S) is the group of all permutations on S.

Let y _g denote the image of g under y .

If x, y Î S, Then x = y iff y _g (x) = y " g Î G.

Note that if y is one-to-one , g Î G may be permutations on S. But, if y is not one-to-one, elements in G could still be permutations on S. However, that would imply there exists distinct elements g, h Î G such that y _g (x) = y _h (x) " x Î S. This means g and h induce the same permutation on S.

Example of group action:

Let S be the 2 diagonals of the square and let G be D₄ (group of symmetries of the square). Then e = Y _{R 0°} , Y _{R 180°} , Y _D, Y _D’

And Y _{R 90°} , Y _{R 270°} , Y _H, Y _V switch the diagonals.

Also, f : g ® Y _g from D₄ to sym (S) is a group homomorphism.

Question: How many ways is it possible to color a regular dodecahedron so that 5 of its faces are black and the other 7 faces are white?

There are 12 total faces, so for 5 black faces, the answer is

12

5

= 12! = 792.

There are 3 types of rotations and the identity. The rotations are in the center of a line (R1), where three vertices meet (R2), in the center of a face of the dodecahedron (R3), and the identity (e). We can count the colorings by making another chart:

Here 60 is the order of G and 840 is the order of fix (g). The order of fix R2 is 0 because R2 does not fix any face and R2 permutes the faces in disjoint 3 cycles. 5 black faces cannot be permuted by disjoint 3 cycles without fixing 2 faces, thus the order of R2 is 0.

The argument is similar for the order of fix R1. Except R1 is a 2 cycle.

Using Burnside’s theorem, we see N = 840/60= 14.

Suppose g is a rigid motion. To review what a rigid motion is, a rigid motion is rotations and reflections that preserve the original shape of the object. Let K be the number of sets of vertices that can take any color. If k can be any arbitrary colors, and a colors are available, then the order of fix (g) = a^k. This implies that k can take arbitrary colors from the cycle representation of g as a permutation on the set S of vertices.

Example:

If we’re using a necklace in D₄, and one of the points is fixed by a rigid motion, and the other three vertices can be any arbitrary color, then the order of fix (g) = number of colors available to the third power. Since there are 3 disjoint cycles in this example, then there will be three factors of the number of colors in fix (g).

A clean definition of cycle index: Suppose that g Î G (where G is a group of permutations). If g breaks down into j₁ cycles of length 1, j₂ cycles of length 2, j_n cycles of length n, then we call (j₁, j₂, …, j_n) the cycle index of g.

The cycle index is a tool for providing a way to use Burnside’s Theorem for counting patterns without having to refer to a list of possible arrangements. That is the order of fix(g) = a^k in Burnside’s equation. Where k is the number of disjoint cycles.

Definition: Cycle index polynomial

Z(G) = 1 å x₁^j1x₂^{j2· · ·} x_n^jn Î Q[x₁, x₂, …, x_n]

G

The proof for this is lengthy, so it won’t be done here, but our result for our hexagon example is:

f(x₁, x₂, …, x_n) = Z(D₆) = (1/12)(x₁⁶ + 3x₁²x₂² + 4x₂³ + 2x₃² +2x⁶)

So, if only two colors are available for our beads, then our equation looks like:

f(2, 2, 2, 2, 2, 2) = Z(D₆) = (1/12)(2⁶ + 3(2)²(2)² + 4(2)³ + 2(2)² + 2(2))

which equals 156/12 = 13.

Thus, we have 13 distinct necklaces.

References:

Gallian, Joseph A. Contemporary Abstract Algebra (Houghton Mifflin Company: Boston, 1998), 490-498.

Gilbert, William J. Modern Algebra With Applications (Wiley-Interscience Publication: New York, 1976), 134-144.

Klima, Richard E. Applications of Abstract Algebra with Maple (CRC Press: Boca Raton, 2000), 192-198.

Lidl, Rudolf. Applied Abstract Algebra (Springer: New York, 1998), 293-298.